LeetCode 137. Single Number II
核心思想
一个 int 型整数有32个二进制位。
- 对于每个二进制位，统计这一位上1的个数，然后对3取余，如果余数不为0，说明不重复的那个数的这个二进制位为1。
- 统计每一位上1的个数，通过和二进制1进行位与操作。
- 如果某个二进制位是1，通过和结果进行
或操作，把这个1添加到结果中对应的二进制位上。
解答1[Java]：
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int i = 0; i < 32; ++i) {
int sum_of_j_digit = 0;
for (int j = 0; j < nums.length; ++j) {
sum_of_j_digit += (nums[j] >> i) & 1;
}
result |= (sum_of_j_digit % 3) << i;
}
return result;
}
}
解答2[Java]：有限状态机
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int num : nums) {
b = b ^ num & ~a;
a = a ^ num & ~b;
}
return a|b;
}
}
最后一句 return 语句如果改为 return b; 也可以得到正确结果。
不过这个算法，同样是有限状态机，其实有好几个写法，不过核心应该都是做一个三进制的计数器。我觉得对我而言是真的很难理解，现在也没有完完全全理解。这里先把几个解释的帖子记下来，等到有时间再来攻克。
An General Way to Handle All this sort of questions.
Detailed explanation and generalization of the bitwise operation method for single numbers